Concerning the problem that existing availability models of Infrastructure as a Service (IaaS) are difficult to calculate the probability of the existence of multiple available Physical Machines (PMs), a new availability analysis method based on Markov process was proposed for IaaS clouds. Firstly, the computing resources were divided into three types:hot PM, warm PM and cold PM. Then, the impact of availability was modeled by combining the corresponding stages of the resource allocation process, separately generating three kinds of allocation sub-models. These sub-models cooperated with each other through the transformation relationships of different types of computing resources, so as to construct the overall model of the system. After that, the availability model was solved by equations constructed based on Markov process. Finally, the proposed analysis model was verified with a practical example, and the key factors such as PM transition rate were analyzed. Experimental results show that, increasing the number of PMs, especially cold PMs helps to improve the availability of IaaS. The proposed method can be used to estimate the probability of the existence of one or multiple available PMs.